package com.mdnote.practice.binary_tree;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/30
 * @description 区间和的个数
 */
public class LeetCode327 {

	private int count;
	private int lower;
	private int upper;

	public int countRangeSum(int[] nums, int lower, int upper) {

		if (nums == null || nums.length == 0) {
			return 0;
		}
		if (lower > upper) {
			return 0;
		}
		this.count = 0;
		this.lower = lower;
		this.upper = upper;

		long[] perSum = new long[nums.length + 1];
		long sum = 0;
		for (int i = 1; i < perSum.length; i++) {
			sum += nums[i - 1];
			perSum[i] = sum;
		}

		mergeSortCount(perSum, 0, perSum.length - 1);
		return this.count;
	}


	private void mergeSortCount(long[] nums, int start, int end) {
		if (start == end) {
			return;
		}
		int mid = start + ((end - start) >> 1);
		mergeSortCount(nums, start, mid);
		mergeSortCount(nums, mid + 1, end);

		_merger(nums, start, mid, end);
		
	}

	private void _merger(long[] nums, int start, int mid, int end) {

		// 计算符合条件的右端点数
		int t = start;  // 左端点
		int l = mid + 1, r = mid + 1;
		while (t <= mid) {
			while (l <= end && nums[l] - nums[t] < this.lower) {
				l++;
			}
			while (r <= end && nums[r] - nums[t] <= this.upper) {
				r++;
			}
			t++;
			this.count += (r - l);
		}

		long[] tmp = new long[end - start + 1];

		int i = start, j = mid + 1, k = 0;
		while (i <= mid && j <= end) {
			tmp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
		}
		while (i <= mid) {
			tmp[k++] = nums[i++];
		}
		while (j <= end) {
			tmp[k++] = nums[j++];
		}
		for (int p = 0; p < tmp.length; p++) {
			nums[start + p] = tmp[p];
		}
	}

	@Test
	public void test_01() {
		LeetCode327 leetCode327 = new LeetCode327();
		// 功能测试
		Assert.assertEquals(3, leetCode327.countRangeSum(new int[]{-2,5,-1}, -2, 2));
		Assert.assertEquals(1, leetCode327.countRangeSum(new int[]{2,5,-1}, 2, 2));
		Assert.assertEquals(1, leetCode327.countRangeSum(new int[]{-2}, -2, 2));
		Assert.assertEquals(4, leetCode327.countRangeSum(new int[]{1, 2, 2, 2}, -2, 2));
		Assert.assertEquals(5, leetCode327.countRangeSum(new int[]{1, 2, 2, 3}, -2, 3));
		// 边界测试
		Assert.assertEquals(5, leetCode327.countRangeSum(new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MIN_VALUE}, Integer.MIN_VALUE, Integer.MAX_VALUE));
		// 负面测试
		Assert.assertEquals(0, leetCode327.countRangeSum(new int[]{}, -2, 2));
		Assert.assertEquals(0, leetCode327.countRangeSum(new int[]{1}, 3, 2));
	}
}